package com.ronz.hashtable;

import java.util.Scanner;

/**
 * @Description 哈希表的基本使用演示
 * @Author Ronz
 * @Date 2021/1/17 8:44
 * @Version 1.0
 */
public class No1_HashTable {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        MyHashTable hashTable = new MyHashTable(6);

        while (true){
            System.out.println();
            System.out.println("(add)添加结点");
            System.out.println("(ser)查找结点");
            System.out.println("(lis)显示结点");
            System.out.println("(del)删除结点");
            System.out.println("(ext)退出");
            System.out.print("请输入选项：");

            String choice = input.nextLine();
            switch (choice){
                case "add":
                    System.out.print("请输入ID：");
                    int id = Integer.parseInt(input.nextLine());
                    System.out.print("请输入姓名：");
                    String name = input.nextLine();
                    hashTable.addEmp(new Employee(id, name));
                    break;
                case "ser":
                    System.out.print("请输入要查找ID：");
                    hashTable.findById(Integer.parseInt(input.nextLine()));
                    break;
                case "lis":
                    hashTable.list();
                    break;
                case "del":
                    System.out.print("请输入要删除ID：");
                    hashTable.deleteById(Integer.parseInt(input.nextLine()));
                    break;
                case "ext":
                    break;
                    default:
                        System.out.println("输入有误！");
            }
        }
    }
}

/**
 * 定义一个哈希表
 */
class MyHashTable{
    private int size;
    private EmployeeLinkedList[] empList;

    public MyHashTable(int maxSize){
        size = maxSize;
        empList = new EmployeeLinkedList[maxSize];
        for (int i=0; i<maxSize; i++){   // 数组中存放的不是基本类型时，必须初始化数组
            empList[i] = new EmployeeLinkedList();
        }
    }

    // 添加一个结点到哈希表中
    public void addEmp(Employee emp){
        int index = hashFun(emp.id);
        empList[index].addEmp(emp);
    }

    // 显示所有结点
    public void list(){
        for (int i=0; i<size; i++){
            System.out.printf("第 %d 个链表为：",i);
            empList[i].list();
            System.out.println();
        }
    }

    // 根据 id 查找某个结点
    public void findById(int id){
        int index = hashFun(id);
        empList[index].findById(id);
    }

    // 根据 id 删除某个结点
    public void deleteById(int id){
        int index = hashFun(id);
        empList[index].deleteById(id);
    }

    // 模拟获取哈希值，改值决定结点要存放到数组的第几个链表
    public int hashFun(int id){
        return id % size;
    }

}

/**
 * 定义一个雇员链表
 */
class EmployeeLinkedList{
    private Employee head = null;   // 这里的头结点是有意义的，是一个真实的雇员

    // 添加结点
    public void addEmp(Employee employee){
        if (head == null){      // 判断链表是否为空
            head = employee;
            return;
        }
        Employee cur = head;    // 辅助指针
        while(cur.next != null){   // 找到最后一个结点
            cur = cur.next;
        }
        cur.next = employee;
        employee.next = null;
    }

    // 通过 id 查找结点
    public void findById(int id){
        if (head == null){  // 判断链表是否为空
            System.out.printf("链表为空， ID 为 %d 的结点不存在！", id);
            return;
        }
        Employee cur = head;    // 第一个结点不能动，要用辅助指针
        while (cur != null){
            if (cur.id == id){
                System.out.printf("找到了！该结点信息为：ID = %d，NAME = %s", id, head.name);
                return;
            }
            cur = cur.next;
        }
        System.out.println("该结点不存在！");
    }

    // 通过 id 删除结点
    public void deleteById(int id){
        if (head == null){
            System.out.println("链表为空，无法删除!");
            return;
        }
        // 因为 head 结点也是一个有效结点，他没有前驱，所以要单独判断
        if (head.id == id){ // 如果第一个结点是目标结点
            head = head.next;
            return;
        }
        // head 之后的节点都是有前驱结点的结点
        Employee cur = head;    // 辅助指针
        while (true){
            if (cur.next == null){  // 如果判断到了最后一个结点还是没有找到
                System.out.println("该结点不存在！");
                return;
            }
            if (cur.next.id == id){
                cur.next = cur.next.next;
                return;
            }
            cur = cur.next;
        }
    }

    // 显示所有结点
    public void list(){
        if (head == null){
            System.out.print("链表为空！");
            return;
        }
        Employee cur = head; // 辅助指针
        while (cur != null){
            System.out.printf(" =>ID：%d，NAME：%s", cur.id, cur.name);
            cur = cur.next;
        }
    }
}

/**
 * 定义一个雇员结点
 */
class Employee{
    public int id;
    public String name;
    public Employee next;

    public Employee(int id, String name){
        this.id = id;
        this.name = name;
    }
}
